package ua.mykola.graph;

import static java.lang.Integer.MAX_VALUE;

import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class DijkstraSP {

	private Graph graph;
	private Vertex vertexFrom;
	private final Map<Vertex, Edge> edgeTo = new HashMap<Vertex, Edge>();
	private final Map<Vertex, Integer> distTo;

	public DijkstraSP(Graph graph, Vertex vertexFrom) {
		this.graph = graph;
		this.vertexFrom = vertexFrom;

		distTo = new HashMap<Vertex, Integer>(graph.getVertices().size());
	}

	private class SmallestDistanceComparator implements Comparator<Vertex> {
		@Override
		public int compare(Vertex o1, Vertex o2) {
			return distTo.get(o1).compareTo(distTo.get(o2));
		}
	}

	public void traverse() {
		Set<Vertex> vertices = graph.getVertices();

		for (Vertex vertex : vertices) {
			distTo.put(vertex, MAX_VALUE);
		}
		distTo.put(vertexFrom, 0);

		SmallestDistanceComparator smallestDistanceComparator = new SmallestDistanceComparator();
		while (!vertices.isEmpty()) {
			Vertex min = Collections.min(vertices, smallestDistanceComparator);
			for (Edge edge : graph.getEdgesFrom(min)) {
				Vertex otherSide = edge.getOtherSide(min);
				if (distTo.get(otherSide) > distTo.get(min) + edge.getWeight()) {
					distTo.put(otherSide, distTo.get(min) + edge.getWeight());
					edgeTo.put(otherSide, edge);
				}
			}
			vertices.remove(min);
		}
	}

	int getWeight(String label) {
		return getWeight(new Vertex(label));
	}

	public int getWeight(Vertex toVertex) {
		return distTo.get(toVertex);
	}

	List<Edge> getPath(String label) {
		return getPath(new Vertex(label));
	}

	public List<Edge> getPath(Vertex vertex) {
		LinkedList<Edge> path = null;
		Vertex currentVertex = vertex;
		Edge edgeUp;
		if (distTo.get(vertex) != MAX_VALUE) {
			path = new LinkedList<Edge>();
			while (!vertexFrom.equals(currentVertex)) {
				edgeUp = edgeTo.get(currentVertex);
				path.addFirst(edgeUp);
				currentVertex = edgeUp.getOtherSide(currentVertex);
			}
		}
		return path;
	}

}
